/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/lucky-number-eight
   @Language: C++
   @Datetime: 19-05-28 10:40
   */

class Solution {
public:
	/**
	 * @param n: count lucky numbers from 1 ~ n
	 * @return: the numbers of lucky number
	 */
	int luckyNumber(int n) {
		// Write your code here
		int factor=log10(n), count=0, part=0;
		if(n>6*pow10(factor)) ++factor;
		for(int i=0; i++<factor; count=9*count+pow(10,i-1));
		for(int i=1+min(n,(int)pow10(factor)); i<=max(n,(int)pow10(factor)); ++i){
			for(int t=i; t; t/=10){
				if(t%10==8){
					++part;
					break;
				}
			}
		}
		return pow10(factor)>n?count-part:count+part;
	}
};
